// m

// 给定一个整数数组nums，要求判断nums中是否存在三个元素a、b、c，满足 a + b + c === 0,找出所有满足要求的不重复的三元组

// 思路：对撞指针

// 时间复杂度：O(n^2)
// 空间复杂度：O(n)

function threeSum(nums) {
    let n = nums.length
    // 先升序排序，保证元素查找不重复且下一步双指针减少一重遍历
    nums.sort((a, b) => a - b)
    let ans = []

    for (let i = 0; i < n; i++) {
        // 重复元素则跳过
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        // left指向下一个位置，right指向末尾位置
        let left = i + 1
        let right = n - 1
        while (left < right) { 
            while (left < right && left > i + 1 && nums[left] === nums[left - 1]) {
                left += 1
            }
            while (left < right && right < n - 1 && nums[right + 1] === nums[right]) {
                right -= 1
            }
            if (left < right && nums[i] + nums[left] + nums[right] === 0) {
                ans.push([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
            } else if (nums[i] + nums[left] + nums[right] > 0) {
                right -= 1
            } else {
                left += 1
            }
        }
    }
    return ans
}

let nums = [-1,0,1,2,-1,-4]
console.log(threeSum(nums))

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum2 = function (nums) {
    nums = nums.sort((x, y) => x - y)
    let res = []
    for (let i = 0; i < nums.length; i++) {
        if(nums[i] > 0) {
            return res
        }
        if (nums[i] === nums[i - 1]) {
            continue
        }
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            if(sum < 0) {
                left++
            } else if(sum > 0) {
                right--
            } else {
                res.push([nums[i], nums[left], nums[right]])
                while(left < right && nums[left] === nums[left+1]){
                    left++
                }
                while(left < right && nums[right] === nums[right - 1]) {
                    right--
                }
                left++
                right--
            }
        }
    }
    return res
};

let nums2 = [-1,0,1,2,-1,-4]
console.log(threeSum2(nums2))
